package backtrackStudy;

import java.util.LinkedList;

/**
 * 要善于学会使用数组连续存储的特性，字符串存储，要么StringBuilder或者直接用char[]
 */
public class GenerateParenthesis {

    private static LinkedList<String> ans = new LinkedList<>();
    /**
     * LeetCode T22 括号生成
     * 题目五：字符串生成
     * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
     * @param args
     */
    public static void main(String[] args) {

    }

    public static LinkedList<String> generateParenthesis(int n){
        //存放路径
        char[] trace = new char[n*2];
        //回溯寻找所有合法的括号组合

        //返回回溯法找到的结果
        return ans;
    }

    //判断括号是否合法，可以不用栈的方式
    private static boolean isValid(char[] cur){
        int balance = 0;
        for (char c : cur) {
            if (c == '('){
                balance++;
            } else {
                balance--;
            }
            if (balance < 0){
                return false;
            }
        }
        return balance == 0;
    }


    //方法一：暴力解法，组合出所有的字符串进行判断，是否合法
    //第一步：确定返回值和参数列表

    /**
     * 该题目不用传入选择列表，遍历是固定的
     * @param n 括号大小，决定深度，
     * @param pos 遍历到的层级，也是位置索引
     * @param trace 记录路径
     */
    public static void backtrace(int n, int pos, char[] trace){
        //定义出口
        if (pos >= 2*n){
            //判断是否合法，然后进行记录
            if (isValid(trace)){
                ans.add(new String(trace));
            }
            return;
        }
        //进行循环，递归
        //选择操作
        trace[pos] = '(';
        backtrace(n, pos+1, trace);
        //取消选择
        trace[pos] = ')';
        backtrace(n, pos+1, trace);
    }
    //方法二：进行剪枝操作，优化回溯结构，新增两个参数，一个是左括号的数量一个是右括号的数量
    public static void backtrace01(int n, int pos, int open, int close, char[] trace){
        //定义出口
        if (pos >= 2*n){
            //判断是否合法，然后进行记录
            if (isValid(trace)){
                ans.add(new String(trace));
            }
            return;
        }
        //进行循环，递归，剪枝操作在循环体进行，根据当前状态判断是否还有必要继续向下回溯
        //选择操作
        if (open <= n ){
            trace[pos] = '(';
            backtrace01(n, pos+1, open+1, close, trace);
        }

        //取消选择
        if (close <= open){
            trace[pos] = ')';
            backtrace01(n, pos+1, open, close + 1, trace);
        }
    }

}
